#include<vector>
#include<algorithm>
using std::vector;
using std::min;



class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < amount+1; i++) {
            for (auto& c: coins) {
                if (c <= i) dp[i] = min(dp[i], dp[i-c]);
            }
            if (dp[i] != INT_MAX) dp[i]++;
        }
        return dp.back() == INT_MAX ? -1 : dp.back();
    }

    
};